package MyDFS;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 39. 组合总和
 *
 * 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 *
 * candidates 中的数字可以无限制重复被选取。
 *
 * 说明：
 *
 *     所有数字（包括 target）都是正整数。
 *     解集不能包含重复的组合。
 *
 * 示例 1：
 *
 * 输入：candidates = [2,3,6,7], target = 7,
 * 所求解集为：
 * [
 *   [7],
 *   [2,2,3]
 * ]
 */
public class Leetcode0039 {
    public static List<List<Integer>> combinationSum(int[] nums, int target) {
        // 首先是特判
        int len = nums.length;
        // 使用一个动态数组保存所有可能的全排列
        List<List<Integer>> res = new ArrayList<>();

        if (len == 0) {
            return res;
        }
        Arrays.sort(nums);

        List<Integer> path = new ArrayList<>();

        // last 上一个值
        dfs(nums, len, target, 0, path, res, -1);
        return res;
    }

    private static void dfs(int[] nums, int len, int target, int total,
                            List<Integer> path,
                            List<List<Integer>> res,int last) {
        if(total > target){
            return;
        }
        if (total == target) {
            // 3、不用拷贝，因为每一层传递下来的 path 变量都是新建的
            res.add(path);
            System.out.println(path.toString());
            return;
        }

        for (int i = 0; i < len; i++) {
            // 1、每一次尝试都创建新的变量表示当前的"状态"
            List<Integer> newPath = new ArrayList<>(path);

            if(total + nums[i] <= target && (last ==-1 || nums[i]>=last)){
                newPath.add(nums[i]);
                dfs(nums, len, target, total + nums[i], newPath, res, nums[i]);
            }

            // 2、无需回溯

        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{2,3,5};
        int target = 8;
        combinationSum(nums, target);
    }
}
